//给定一个带有头结点 head 的非空单链表，返回链表的中间结点。 
//
// 如果有两个中间结点，则返回第二个中间结点。 
//
// 
//
// 示例 1： 
//
// 输入：[1,2,3,4,5]
//输出：此列表中的结点 3 (序列化形式：[3,4,5])
//返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
//注意，我们返回了一个 ListNode 类型的对象 ans，这样：
//ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = 
//NULL.
// 
//
// 示例 2： 
//
// 输入：[1,2,3,4,5,6]
//输出：此列表中的结点 4 (序列化形式：[4,5,6])
//由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
// 
//
// 
//
// 提示： 
//
// 
// 给定链表的结点数介于 1 和 100 之间。 
// 
// Related Topics 链表

package leetcode.editor.cn;
public class MiddleOfTheLinkedList {
    public static void main(String[] args) {
        Solution solution = new MiddleOfTheLinkedList().new Solution();
        ListNode listNode =
                ListNodeUtil.constructList(new int[]{1, 2, 3, 4, 5,6});
        ListNode node = solution.middleNode(listNode);
        ListNodeUtil.printList(node);
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 1,2,3,4,5 中间为3
     * 1,2,3,4,5,6 中间为4
     *
     * 1. 快慢指针都指向head；快指针不为null
     * 2. 慢的先走一步；快的两步
     * 3. 当快的next.next已经为null了，说明是偶数节点；此时，直接取慢指针的值
     * 4. 当快的next，已经为null了，说明是奇数节点；此时，直接取慢指针的值
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode tempSlow;
        while (fast != null) {
            tempSlow = slow;

            slow = slow.next;
            fast = fast.next;
            if (fast == null) {
                return tempSlow;
            }
            fast = fast.next;
            if (fast == null) {
                return slow;
            }
        }

        return null;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}